1. Field of the Invention
The invention relates to a motion estimation method in video processing, more particularly to a motion estimation method utilizing a modified rhombus pattern search for a succession of frames in a digital coding system.
2. Description of the Related Art
Referring to FIG. 1, the data structure of a data stream of an MPEG coded video is shown to be formed from one or more sequences. Each sequence includes one or several groups of pictures (GOP), which refers to a group consisting of a plurality of pictures or frames. These pictures or frames can be classified into three types, i.e., intra-coded frames (I frame), predictive-coded frames (P frame), and bi-directionally predictive-coded frames (B frame), according to their attributes.
Each of the aforesaid frames can be encoded. Generally, I frames are used as cut-in points during video compression. A P frame can be predicted through motion estimation using an I frame or another P frame as a reference frame, whereas a B frame can be predicted from the motion vectors generated by both an I frame and a P frame or by two P frames which serve as reference frames. Thus, by presenting the frames successively, the MPEG video can be presented to a user.
In MPEG compression standards, each frame is divided into a plurality of slices. Each slice is further divided into a plurality of macroblocks (MB). Each macroblock is composed of four luminance blocks and a plurality of chrominance blocks. Each block is defined as the smallest coded unit of the MPEG data structure. The corresponding inverse operation of motion compensation in MPEG video coding is motion estimation. The most direct way of implementing motion estimation is to record the luminance and chrominance of each pixel in a macroblock or in a block, and use the information in a full search to find the best matched motion vector in the search area. However, such a scheme involves consumption of large amounts of resources.
With the use of motion estimation, the blocks in the current frame can be reconstructed by 1) shifting the best-matched blocks in the reference frame with the motion vectors found in the aforesaid motion estimation as well as 2) the small differential data between blocks in the current frame and best-matched blocks in the reference frame. Since it is not necessary to store a large amount of redundant data, the amount of stored data can be reduced to thereby achieve the object of data compression. Current motion estimation methods include the Full Search (FS), the Three-Step Search (TSS), the Four-Step Search (FSS), and the Diamond Search (DS).
In the conventional Diamond Search (DS), a search area in either one of the two diamond patterns is searched. This search scheme involves the following steps:
Step 1: An origin point and eight other points that surround the origin point and that lie on the boundary of a hollow diamond-shaped search area are found so that there are altogether nine search points. If the best matched point is found to be at the center of the search area, the flow proceeds to step 4. On the other hand, if the best matched point is found to be on the boundary of the search area, the flow proceeds to step 2.
Step 2: Set the center to the best matched point found in step 1, and continue the search using the hollow diamond-shaped search area.
Step 3: If the best matched point is still found to be at the center of the new search area, step 4 is performed. On the other hand, if the new best matched point is found to be on the boundary of the new search area, step 2 is repeated.
Step 4: The search area is reduced to a smaller solid diamond. The search is stopped because the (local) best matched point is found.
The aforesaid scheme is further illustrated with reference to FIG. 2A. In step 1, the initial best matched point is found to be at the center (1a) of the search area, and step 4 is therefore performed in the reduced search area, a smaller solid diamond. The search is ended when the (local) best-matched point (2a) is located.
Referring to FIG. 2B, when the initial best matched point (1b) in step 1 is found to be located on the boundary of the search area, step 2 is performed to form another hollow diamond-shaped search area centered at the initial best matched point (1b). Then step 3 is performed. Since the new best matched point (2b) is found to lie on the boundary of the new search area, step 2 is repeated to form yet another hollow diamond-shaped search area centered at the new best matched point (2b). When it is found that the latest best matched point is located at the center of the search area, step 4 is performed in the reduced search area, a smaller solid diamond. The search is ended when the ideal point (4b) is found.
However, in the conventional diamond search scheme, as the search begins with blocks on the boundary of a larger hollow diamond centered at an origin point before searching blocks in a smaller solid diamond, where probabilities that the best matched block is located are higher, the search efficiency is relatively low.